nowcoder163 B-Matrix Multiplication （矩阵快速幂 模板）

发表于 | 更新于: | 分类于 ， | | 阅读次数: |
字数统计: 759 | 阅读时长 ≈ 5

描述

传送门：B-Matrix Multiplication

In mathematics, matrix multiplication or matrix product is a binary operation that produces a matrix from two matrices with entries in a field, or, more generally, in a ring or even a semiring. The matrix product is designed for representing the composition of linear maps that are represented by matrices. Matrix multiplication is thus a basic tool of linear algebra, and as such has numerous applications in many areas of mathematics, as well as in applied mathematics, physics, and engineering. In more detail, if A is an n x m matrix and B is an m x p matrix, their product AB is an n x p matrix, in which the m entries across a row of A are multiplied with the m emtries down a column of B and summed to produce an entry of AB. When two linear maps are represented by matrices, then the matrix product represents the composition of the two maps.
We can only multiply two matrices if their dimensions are compatible, which means the number of columns in the first matrix is the same as the number of rows in the second matrix.
If A is an n x m matrix and B is an m x p matrix,

the matrix product C = AB is defined to be the n x p matrix

such that

,
for i = 1,2, …, n and j = 1,2, …, p.
Your task is to design a matrix multiplication calculator to multiply two matrices and
display the output. If the matrices cannot be multiplied, display “ERROR”.

输入描述

The first line of the input is T(1≤ T ≤ 100), which stands for the number of test cases you need to solve.
For each test case, the first line contains four integers m, n, p and q (1 ≤ m,n,p,q ≤ 20). m and n represent the dimension of matrix A, while p and q represent the dimension of matrix B.
The following m lines consist of the data for matrix A followed by p lines that contains the data for matrix B. (-100 ≤ aij ≤ 100, -100 ≤ bij ≤ 100).

输出描述

For each test case, print the case number and the output of the matrix multiplication.

示例

输入

1
2
3
4
5
6
7
8
9
10
11
12
2
2 3 3 2
1 1 1
1 2 3
2 3
4 5
6 7
2 3 2 3
1 2 3
1 2 3
2 3 4
2 3 4

输出

1
2
3
4
5
Case 1:
12 15
28 34
Case 2:
ERROR

题解

题目大意

矩阵相乘

思路

模板题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
typedef long long lint;
const int MAXN = 25, INF = 0x3f3f3f3f;
using namespace std;
struct Mat{
    int n, m;
    int mat[MAXN][MAXN];
    Mat(){
        memset(mat, 0, sizeof(mat));
        n = m = MAXN;
    };
    Mat operator * (Mat b){
        Mat c;
        c = Mat();
        c.n = n;
        c.m = b.m;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=b.m; ++j){
                for(int k=1; k<=m; ++k){
                    c.mat[i][j] += mat[i][k]*b.mat[k][j];
                }
            }
        return c;
    }
    Mat operator + (Mat b){
        Mat c;
        c.n = n;
        c.m = m;
        for (int i=1; i<=n; ++i)
            for (int j=1; j<=m; ++j)
                c.mat[i][j] = mat[i][j] + b.mat[i][j];
        return c;
    }
    void in(int x, int y){
        n = x;
        m = y;
        for(int i=1; i<=x; ++i)
            for(int j=1; j<=y; ++j)
                scanf("%d", &mat[i][j]);
    }
    void out(){
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=m; ++j)
                printf("%d ", mat[i][j]);
            puts("");
        }
    }
};
 
 
int main(){
    int t, n, m, p, q;
    scanf("%d", &t);
    Mat a, b, c;
    for(int d = 1; d <= t; d++){
        scanf("%d %d %d %d", &n, &m, &p, &q);
        a.in(n, m);
        b.in(p, q);
        printf("Case %d:\n", d);
        if(m != p){
            printf("ERROR\n");
        }
        else{
            c = a*b;
            c.out();
        }
    }
}